윌슨의 정리

대부분의 정수론 교재에 등장하는 정리. 이름은 수학자 존 윌슨의 이름을 땄다. 1770년에 수학자 에드워드 웨어링(Edward Waring)이 이 정리를 발표했으나, 자기 자신이나 제자 윌슨도 증명을 하지 못했다. 일단 공식적인 첫 증명은 1771년에 라그랑주에 의해 발표되었다. 자세한 정리는 아래와 같다.

이 방법은 소수 판정법에 이용할 수 있으나 팩토리얼을 구하는 시간에 1부터 제곱근까지 하나씩 나눠보는 게 빠르다.

증명에 앞서 합동식에 관한 내용과 잉여계, 잉여역수에 관한 내용을 꼭 알아야 한다. 먼저 도움정리부터 증명하자.

증명

$p$가 소수라고 가정하자. 그럼 임의의 $k\in\left\{1,2,\cdots,p-1\right\}$에 대하여 $k$와 $p$는 서로소이다. 그러므로 적당한 정수 $a,b$에 대해 $ak+bp=1$이 성립하고,[1] 곧 $ak\equiv1\left(\text{mod}\,p\right)$이다. 법 $p$에 대하여 $a\in\left\{1,2,\cdots,p-1\right\}$이므로 $\left\{1,2,\cdots,p-1\right\}$의 모든 원소의 법 $p$에 대한 잉여역수는 같은 집합의 원소이다. 특히, 도움정리에 의해 $1$과 $p-1$은 자기 자신이 잉여역수이다. 나머지 $2,3,\cdots,p-2$는 두 원소씩 쌍으로 법 $p$에 대해 잉여역수 관계이고, 따라서 $\left(p-1\right)!\equiv1\cdot2\cdots\left(p-2\right)\cdot\left(p-1\right)\equiv1\cdot1\cdot\left(p-1\right)\equiv p-1\equiv -1\left(\text{mod}\,p\right)$이다.

역으로 $\left(p-1\right)!\equiv-1\left(\text{mod}\,p\right)$라고 가정하자. 그러면 $\left(p-1\right)!+1=kp$를 만족하는 정수 $k$가 존재한다. $p=ab,\,\left(1\leq a,b\leq p\right)$라 가정하자. 만약 $a=p$이면 $b=1$이고 이는 곧 $p$가 소수임을 의미한다. $a<p$라고 가정하면, $a\in\left\{1,2,\cdots,p-1\right\}$이므로 $a\mid\left(p-1\right)!$이다. 그리고 $a\mid p$이고, $\left(p-1\right)!+1=kp$이므로 $a\mid1$이다. 이를 모두 만족하는 값은 $a=1$밖에 없고, 따라서 $b=p$이다. 곧 $p$는 소수이다.

17!을 19로 나눈 나머지를 구해보자. 먼저 정리를 쓰면, $18!\equiv-1\left(\text{mod}\,19\right)$이다. 또한, $18\equiv-1\left(\text{mod}\,19\right)$이므로, $-1\equiv18!\equiv18\times17!\equiv\left(-1\right)\times17!\left(\text{mod}\,19\right)$이다. 따라서 $17!\equiv1\left(\text{mod}\,19\right)$이다.